N-repeated element in size 2N array [Count, Compare]

Time: O(N); Space: O(1); easy

In a array A of size 2N, there are N+1 unique elements, and exactly one of these elements is repeated N times.

Return the element repeated N times.

Example 1:

Input: A = [1,2,3,3]

Output: 3

Example 2:

Input: A = [2,1,2,5,3,2]

Output: 2

Example 3:

Input: A = [5,1,5,2,5,3,5,4]

Output: 5

Notes:

  • 4 <= len(A) <= 10000

  • 0 <= A[i] < 10000

  • len(A) is even

1. Count

Intuition and Algorithm Let’s count the number of elements. We can use a HashMap or an array - here, we use a HashMap. After, the element with a count larger than 1 must be the answer.

[1]:

import collections

class Solution1(object):
    """
    Time: O(N), where N is the length of A.
    Space: O(N).
    """
    def repeatedNTimes(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        count = collections.Counter(A)
        for k in count:
            if count[k] > 1:
                return k

[2]:

s = Solution1()
A = [1,2,3,3]
assert s.repeatedNTimes(A) == 3
A = [2,1,2,5,3,2]
assert s.repeatedNTimes(A) == 2
A = [5,1,5,2,5,3,5,4]
assert s.repeatedNTimes(A) == 5

2. Compare

Intuition and Algorithm If we ever find a repeated element, it must be the answer. Let’s call this answer the major element.

Consider all subarrays of length 4. There must be a major element in at least one such subarray.

This is because either: * There is a major element in a length 2 subarray, or; * Every length 2 subarray has exactly 1 major element, which means that a length 4 subarray that begins at a major element will have 2 major elements. Thus, we only have to compare elements with their neighbors that are distance 1, 2, or 3 away.

[5]:

class Solution2(object):
    """
    Time: O(N), where N is the length of A.
    Space: O(1).
    """
    def repeatedNTimes(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        for k in range(1, 4):
            for i in range(len(A) - k):
                if A[i] == A[i+k]:
                    return A[i]

[6]:

s = Solution2()
A = [1,2,3,3]
assert s.repeatedNTimes(A) == 3
A = [2,1,2,5,3,2]
assert s.repeatedNTimes(A) == 2
A = [5,1,5,2,5,3,5,4]
assert s.repeatedNTimes(A) == 5

[7]:

class Solution3(object):
    def repeatedNTimes(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        for i in range(2, len(A)):
            if A[i-1] == A[i] or A[i-2] == A[i]:
                return A[i]
        return A[0]

[8]:

s = Solution3()
A = [1,2,3,3]
assert s.repeatedNTimes(A) == 3
A = [2,1,2,5,3,2]
assert s.repeatedNTimes(A) == 2
A = [5,1,5,2,5,3,5,4]
assert s.repeatedNTimes(A) == 5